package lc279;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Lc279_3 {

    /**
     * BFS要点
     * 1、需要用队列记录访问中的节点。
     * 2、需要用集合记录访问过的节点(hashmap、数组都可以)
     * 3、用while来不断循环，直到得出结果
     * 4、return 层数
     * 这题重点：curr+j*j 这个在动态规划里面称之为转移变量，也是这个题目的核心，
     * time:O(N)
     * space:O(N)
     * spend:30min
     */
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        // 记录访问过的节点
        Set<Integer> isVisit = new HashSet<>();
        int level = 0;
        queue.add(0);
        while(!queue.isEmpty()){
            int size = queue.size();
            level++;
            for(int i = 0; i < size; i++){
                int curr = queue.poll();
                for(int j = 1; j <= n; j++){
                    int value = curr + j * j;
                    if(n == value){ // 当value=n时，说明这个leven就是最短的了。可以直接return
                        return level;
                    }
                    if(value > n){ // 当value>n，终止内层循环
                        break;
                    }
                    if(!isVisit.contains(value)){
                        isVisit.add(value);
                        queue.offer(value);
                    }
                }
            }
        }
        return level;
    }

}
